package Point.SlipWindow;

import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * A D O B E C O D E B  A  N  C - ABC
 * 0 1 2 3 4 5 6 7 8 9 10 11 12
 *             走到6不对，应该走到B，不光剔除ABC 还要走到下一个ABC任一出现处
 * A D O B E C
 * 0         5
 * l         r r(到 w2 r超一个)
 *   l l l           B
 *           r r r r r r{Character@1204} C -> {Integer@1202} 1
 *       l l l          A
 *                   r  r  r
 *
 * 总结：
 *  LBLD:
 *      1 Map 初始化 0 , 防止 后面 空指针 处理麻烦
 *   ** 2
 *          ...12 以 needMap 为核心
 *          (1) needMap.contains
 *          (2) windowMap 只统计 needMap 的 key -> 减少bug / 提速
 *
 *
 *  自:
 *    * 0 left一直走到下个ABC处 并不是优化 而是 *必须* 思路! (卡点)
 *
 *      1 只要 通过样例 >= 20% , 证明 框架是对的 ， 改动小组件 即可
 *
 *      2 while 难理解 -> while ( 里面的条件 ) 汉译出来 给 体 念
 *
 *      3 为何 r) ?
 *         char curRight = s.charAt(right); // cur 含 r
 *         right++; // r多1 进入 left , 所以debug [l,r)
 *
 *
 *   -> 能用 nedMap 就用 ！
 *   -> 还是我自己的 while left 好理解 （valid 难理解 要用汉译）
 *
 */
public class 最小覆盖子串76 {
    /**
     * [MH 解法] -> 255/256
     */
    // 全局： T 的 charNumMap
    Map<Character, Integer> TcharNumberMap = new HashMap<>();
    // × 按个数比 不是个数完全一样 ，而是 >=
    public boolean isContainsAndCharNumBigThanAllT(Map<Character, Integer> charNumberMap, String t){
        char[] tChars = t.toCharArray();
        for (int i = 0; i < tChars.length; i++) {
            /**
             * 关键 if ：
             *  1 此时right) 没包进去的 containKey 防止 get null
             *  2 大概率 个数不是完全一样 有几个字母多几个 BBAAC BAC
             *  3 有可能有 key 但是 被 left 减到0个了
             */
            if(!charNumberMap.containsKey(tChars[i])
                    || charNumberMap.get(tChars[i]) < TcharNumberMap.get(tChars[i])
                    || charNumberMap.get(tChars[i]) == 0 ) {
                return false;
            }
        }
        return true;
    }
    public String minWindow2(String s, String t) {
        // 全局 t Map 个数 -> 给 isContainsAllT 用
        for(char Tchar : t.toCharArray() ) {
            TcharNumberMap.put(Tchar, TcharNumberMap.getOrDefault(Tchar, 0) + 1);
        }
        // 正式开始
        Map<Character, Integer> charNumberMap = new HashMap<>();
        int left = 0, right = 0;
        int resMinLen = s.length();
        String resMinStr = "";
        // tSet
        char[] chars = t.toCharArray();
        Set<Character> tCharSet = new HashSet<>();
        for(char c :chars) {
            tCharSet.add(c);
        }
        // left-window
        while (right < s.length()) {
            char curRight = s.charAt(right); // cur 含 r
            right++; // r多1 进入 left , 所以debug [l,r)
            // ...1
            charNumberMap.put(curRight, charNumberMap.getOrDefault(curRight, 0) + 1);
            // debug
            System.out.println(String.format("-> [%s,%s)\n", left,right));

             // right-window
            /**
             * // boolean isFirstExe = true;  不应该写
             *
             * 汉译 while isContainsAllT
             * 包含 全部 target 的 set
             * 就应该 更新 minStr
             */
            while (isContainsAndCharNumBigThanAllT(charNumberMap, t)){
                // 汉： 只要 符合 w 包含全部 AllT，就该 更新 minStr
                if( right - left <= resMinLen ) {
                    resMinLen = right - left;
                    resMinStr = s.substring(left, right);
                }
                // ...2
                char curLeft = s.charAt(left);
                //对应个数-1
                charNumberMap.put(curLeft, charNumberMap.get(curLeft) - 1);
                //减到0 出发 while内部小函数 退出
                left++;

                // left走到下一个ABC处 （这不是为解决 特例 产生的， 而是 必须 操作）
                while (left < s.length() && !tCharSet.contains(s.charAt(left))) {
                    left ++;
                }
            }
        }
        return resMinStr;
    }

    /**
     * [LBLD 解法] -> ac
     */
    public String minWindow_LBLD(String s, String t) {
        Map<Character, Integer> needMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            needMap.put(c , needMap.getOrDefault(c, 0) + 1);
        }
        Map<Character, Integer> windowMap = new HashMap<>();
        for (char c : s.toCharArray()) { // 防 key 字符 空指针
            windowMap.put(c, 0);
        }

        int left = 0, right = 0;
        int validNum = 0;  // 这个 valid 相当于 我的 while left一直右
        int minLen = s.length();
        String minStr = "";

        while (right < s.length()) {
            char curRight = s.charAt(right);
            right ++ ;
            if (needMap.containsKey(curRight)) { // 这里细节很多 (用 ’对称‘ 检查 ？ )
                windowMap.put(curRight , windowMap.get(curRight) + 1);
                if (windowMap.get(curRight).equals(needMap.get(curRight))) {
                    validNum += needMap.get(curRight); // aa aa LBLD错
                }
            }

            System.out.println(String.format("-> [%s,%s)", left, right));

            while (validNum == t.length()) {
                if (right - left <= minLen) {
                    minLen = right - left;
                    minStr = s.substring(left, right);
                }
                char curLeft = s.charAt(left);
                left ++ ;
                if (needMap.containsKey(curLeft)){ // ned核心
                    if(windowMap.get(curLeft).equals(needMap.get(curLeft))) { // ~ win只统计ned的
                        validNum -= needMap.get(curLeft);; // 这只能靠题感做, 纯草纸想 2个小时把，笔试时间不够 （ aa aa LBLD错）
                    }
                    windowMap.put(curLeft, windowMap.get(curLeft) - 1); // 后-validNum, 因为只有 num *恰好*相等时 能 减一个vaild
                }
            }
        }
        return minStr;
    }

    @Test
    public void test() {
        String s = "ADOBECODEBANC", t = "ABC";
        // System.out.println("RES:" + minWindow_LBLD(s, t));
        System.out.println("RES:" + minWindow_LBLD("aa", "aa"));
        String s2 = "ADOBECODEBAN C" , t2 = "ABC";
        // System.out.println(minWindow("a", "aa"));
        // System.out.println("RES:" + minWindow2("ab", "a"));
        // System.out.println("RES:" + minWindow2("ab", "b"));
    }
}
